package leetcode.hot100;

@SuppressWarnings("all")
public class _33_搜索旋转排序数组 {

    // 要求时间复杂度为O(log^n)，暗示可以使用二分查找的方式来解决
    // nums = [4,5,6,7,0,1,2], target = 0，返回结果=4
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            // 定位中轴元素---7
            int mid = (left + right) >> 1;
            // 0是小于7的，按理说应该往左区间继续查找，但是这种情况明显是往右区间查找，所以得判断
            // 隐藏：中轴元素所在的区间一定是升序的
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) {
                // 确定[left,mid]范围是有序的
                // 在确定有序区间的前提下判断目标元素是否在此区间
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 确定[mid,right]范围是有序的
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
